The Diffie-Hellmann key exchange cryptographic protocol is used to exchange keys securely between two entities. Using it entails employing a group in the mathematical sense of the term. A group that can be used is constituted by an elliptic curve of the following type:y2+xy=x3+αx2+β
It is known that if P=(x,y) is on the elliptic curve E, it is possible to define a “product” or “scalar multiplication” of the point P of E by an integer m. This operation is defined as follows:[m]P=P+P+P . . . +P(m times)
Doubling a chosen point P on this kind of elliptic curve in a Diffie-Hellmann key exchange algorithm is known in the art. This operation is known as “point doubling” and is part of an iterative double-and-add process. Any such doubling takes time.
The slowest part of the Diffie-Hellman key exchange protocol is multiplying an unknown point on the curve by a random scalar. Only elliptic curves defined on a body of characteristic-two are considered here; this is a widely adopted implementation choice, because addition within a body of this kind corresponds to the “exclusive—or” operation.
It is known in the art that multiplication by a scalar can be accelerated for curves defined on a body of low cardinality by using the Frobenius morphism. The curves can be chosen so that none of the known attacks applies to them. However, it is obviously preferable, at least in principle, to be able to choose the curve to be used from a class of curves that is as general as possible. The fastest version of the method in accordance with the invention is applied to half the elliptic curves. Moreover, from a cryptographic point of view, that half is the best half. Before the theory of the method is described, the basic concepts are reviewed.
For simplicity, consider the elliptic curve (E) that can be represented geometrically and is defined for the set R of real numbers by the equation y2+y=x3−x2 shown in FIG. 1, in which figure a horizontal line represents an integer number m, a vertical line represents an integer number n and each intersection of horizontal and vertical lines represents the integer coordinate pair (m, n).
(E) passes through a finite number of points with integer coordinates and any secant at (E) originating from any such point intersects (E) at two points, which may be coincident (in the case of tangents to the curve).
The addition operation applied to any two of these points A and B is defined as follows: let B1 be the point at which the straight line segment (AB) intersects (E); the vertical through B1 intersects (E) at C=A+B.
In the special case where (AB′) is tangential to (E), C′ is the required sum.
The “intersection of all verticals” point O is referred to as the point at infinity of (E) and is the neutral element of the addition defined in this way since, by applying the geometrical construction which defines the addition:A+O=O+A=A 
The doubling of A, which is denoted [2]A and defined as: A+A, is therefore the point B′, the straight line segment (Ax) being tangential to (E) at A.
By applying the addition of A construction to the point B′, the point [3]A is obtained, and so on: this is the definition of the product [n]A of a point by an integer.
The present invention in fact relates to a family of elliptic curves which cannot be represented geometrically but are defined as follows:
Let n be a given integer, F2n the body of 2n elements, and {overscore (F2n)} its algebraic closure. Let O be the point at infinity. The non-supersingular elliptic curve E defined at F2n is:E={(x,y)ε{overscore (F2n)}×{overscore (F2n)}|y2+xy=x3+αx2+β}∪{O}α, βεF2n,β≠0
The elements of E are usually referred to as “points”. It is well known in the art that E can be given an abelian group structure by taking the point at infinity as a neutral element. Hereinafter, the finite subgroup of rational points of E is considered, and is defined by:E(F2n)={(x,y)εF2n×F2n|y2+xy=x3+αx2+β}∪{O}α, βεF2n,β≠0where N is the set of natural integers; for all mεN, the “multiplication by m” application in E is defined by:[m]:E→EP→P+ . . . +P(m times) and ∀PεE:[O]P=O
E[m] is the kernel of the application. The points of the group E[m] are called the m-torsion points of E. The group structure of the m-torsion points is well known in the art.
In the situation in which m is a power of 2:∀kεN:E[2k]≅Z/2kZ where Z is the set of relative integers.
Because E(F2n) is a finite sub-group of E, there exists k′≧1 such that E(2k) is contained in E(F2n) if and only if k≦k′. For the elliptic curves E for which k′=1, the structure of E(F2n) is:E(F2n)=G×{O, T2}where G is an odd order group and T2 designates the unique second order point of E. A curve of this kind is said to have a minimal two-torsion.